package com.leetcode;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
/**
 * Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.

The Sudoku board could be partially filled, where empty cells are filled with the character '.'.


A partially filled sudoku which is valid.

Note:
A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.
 * @author Adiy
 *
 */
public class ValidSudoku {

	public static void main(String[] args) {
//		char[][] board={
//				".87654321".toCharArray(),
//				"1........".toCharArray(),
//				"2........".toCharArray(),
//				"3........".toCharArray(),
//				"4........".toCharArray(),
//				"5........".toCharArray(),
//				"6........".toCharArray(),
//				"7........".toCharArray(),
//				"8........".toCharArray(),
//		};
		//["....5..1.",".4.3.....",".....3..1","8......2.","..2.7....",".15......",".....2...",".2.9.....","..4......"]
		char[][] board1={
				"....5..1.".toCharArray(),
				".4.3.....".toCharArray(),
				".....3..1".toCharArray(),
				"8......2.".toCharArray(),
				"..2.7....".toCharArray(),
				".15......".toCharArray(),
				".....2...".toCharArray(),
				".2.9.....".toCharArray(),
				"..4......".toCharArray(),
		};
		System.out.println(isValidSudoku(board1));
		
	}
	public static boolean isValidSudoku(char[][] board) {

		int lenr=board.length;
		int lenc=board[0].length;
		for(int i=0;i<lenr;i++){
			List<Integer> list=new ArrayList<Integer>();
			for(int j=0;j<lenc;j++){
				if(board[i][j]!='.'){					
					list.add(Integer.parseInt(board[i][j]+""));
					if(hasTheSame(list))  return false;
				}
			}
		}
		
		for(int i=0;i<lenc;i++){
			List<Integer> list=new ArrayList<Integer>();
			for(int j=0;j<lenr;j++){
				if(board[j][i]!='.'){
					list.add(Integer.parseInt(board[j][i]+""));
					if(hasTheSame(list))  return false;
				}
			}
		}
		
		for(int i=0;i<lenr-2;i+=3)
		for(int j=0;j<lenc-2;j+=3){
			List<Integer> list=new ArrayList<Integer>();
			for(int k=0;k<3;k++){
				for(int n=0;n<3;n++){
					if(board[i+k][j+n]!='.'){
						list.add(Integer.parseInt(board[i+k][j+n]+""));
						if(hasTheSame(list))  return false;
					}
				}
				
			}
			//i+=3;j+=3;
			
		}
		return true;
	}
	public static boolean hasTheSame(List num){
		Set<Integer> numSet=new HashSet<Integer>();
		for(int i=0;i<num.size();i++){
			numSet.add((Integer) num.get(i));
		}
		if(num.size()==numSet.size()) return false;
		else return true;
	}
}
